package me.mingshan.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * https://leetcode.cn/problems/add-one-row-to-tree/description/
 * <p>
 * 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
 * <p>
 * 注意，根节点 root 位于深度 1 。
 * <p>
 * 加法规则如下:
 * <p>
 * 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
 * cur 原来的左子树应该是新的左子树根的左子树。
 * cur 原来的右子树应该是新的右子树根的右子树。
 * 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
 *
 * @author hanjuntao
 * @date 2025/9/3 0003
 */
public class L_623_在二叉树中新增一行 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(1);
        root.right.left = new TreeNode(5);

        int val = 1;
        int depth = 2;

        TreeNode newRoot = addOneRow(root, val, depth);
        TreeNode.print(newRoot);
    }

    /**
     * 思路：
     *
     * 由于是在指定深度添加节点，那么就是从根节点开始，逐层遍历，直到指定深度。
     *
     * 然后指定深度添加节点，同时上个节点的左右节点指向新加的节点，新加的节点的左右节点指向原节点的左右节点
     *
     * @param root
     * @param val
     * @param depth
     * @return
     */
    public static TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }

        calDep2(root, val, depth);
        return root;
    }

    private static void calDep2(TreeNode root, int val, int depth) {
        // 层序遍历逻辑：
        // 当遍历当前层时，将当前层的左右节点加入队列
        // 如何知道有没有遍历完当前层呢？

        // 层数
        int level = 0;
        // 当前层节点总数
        int curLevelNodesTotal = 0;
        // 当前层遍历的节点个数
        int curLevelCntNode = 0;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        level++;
        curLevelNodesTotal++;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            // 遍历到指定层的上一层
            if (level == depth -1) {
                TreeNode left = node.left;
                TreeNode right = node.right;

                TreeNode newNodeLeft = new TreeNode(val);
                TreeNode newNodeRight = new TreeNode(val);

                node.left = newNodeLeft;
                node.right = newNodeRight;

                newNodeLeft.left = left;
                newNodeRight.right = right;
            }

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            curLevelCntNode++;

            // 当前层遍历结束
            if (curLevelCntNode == curLevelNodesTotal) {
                level++;
                curLevelNodesTotal = queue.size();
                curLevelCntNode = 0;
            }
        }
    }
}
